class Solution {
public:
    vector<vector<int>> memo; // the most points the first player can win 
    bool PredictTheWinner(vector<int>& nums) {
        int s = nums.size();
        memo = vector<vector<int>>(s, vector<int>(s, INT_MAX));
        return dp(0, s - 1, nums) >= 0;
    }
    int dp(int i, int j, vector<int>& nums) {
        if(memo[i][j] == INT_MAX) 
        {
            if (i == j)
                memo[i][j] = nums[i];
            else
                memo[i][j] = max(nums[i] - dp(i + 1, j, nums), nums[j] - dp(i, j - 1, nums));
        }
        return memo[i][j];
    }
};
